package leetcode.pre100;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
 * <p>
 * 示例 1:
 * <p>
 * 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
 * 输出: true
 * 示例 2:
 * <p>
 * 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
 * 输出: false
 * <p>
 * 注意：交错指的是，对于s1中的相对次序，在s3中也要体现
 *
 * @since 2020/6/11 0011 下午 4:24
 */
public class Code97_交错字符串 {
    public static void main(String[] args) {
        String s1 = "aabcc";
        String s2 = "dbbca";
        String s3 = "aadbbcbcac";

        System.out.println(isInterleave4(s1, s2, s3));
        HashMap<Object, Object> map = new HashMap<>();
        map.put(1, 1);
        System.out.println(map.size());
        map.remove(1);
        System.out.println(map.size());
    }

    /**
     * 思路1：使用Map存储s3,遍历s1和s2剔除。错误点，没有考虑s1在s3中的相对次序不变
     */
    public static boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s3.length(); i++) {
            map.put(s3.charAt(i), map.getOrDefault(s3.charAt(i), 0) + 1);
        }
        for (int i = 0; i < s1.length(); i++) {
            char c = s1.charAt(i);
            if (!map.containsKey(c)) return false;
            int count = map.get(c);
            if (count == 0) return false;
            if (count == 1) {
                map.remove(c);
            } else {
                map.put(c, count - 1);
            }
        }
        for (int i = 0; i < s2.length(); i++) {
            char c = s2.charAt(i);
            if (!map.containsKey(c)) return false;
            int count = map.get(c);
            if (count == 0) return false;
            if (count == 1) {
                map.remove(c);
            } else {
                map.put(c, count - 1);
            }

        }
        return map.size() == 0;
    }

    /**
     * 思路2：利用3个指针匹配，注意s3处可能匹配到s1或s2，没有考虑是先匹配s1还是s2
     */
    public static boolean isInterleave2(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        int p3 = 0;
        int p2 = 0;
        int p1 = 0;
        while (p3 < s3.length()) {
            char c = s3.charAt(p3);
            //这里默认先来匹配s1，会产生错误，有可能先匹配s2
            if (p1 < s1.length() && c == s1.charAt(p1)) {
                p1++;
            } else if (p2 < s2.length() && c == s2.charAt(p2)) {
                p2++;
            } else {
                return false;
            }
            p3++;
        }
        return true;
    }

    /**
     * 思路3：利用3个指针匹配，注意s3处可能匹配到s1或s2，都要考虑，所以采用递归
     * 重复计算的地方：当来到p3处，能否匹配到p1或p2已经是固定的了
     */
    public static boolean isInterleave3(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        return process(0, s1, 0, s2, 0, s3);
    }

    private static boolean process(int p1, String s1, int p2, String s2, int p3, String s3) {
        if (p3 == s3.length()) return true;
        if (p1 == s1.length()){
            return s2.substring(p2,s2.length()).equals(s3.substring(p3,s3.length()));
        }
        if(p2 == s2.length()){
            return s1.substring(p1,s1.length()).equals(s3.substring(p3,s3.length()));
        }
        char c = s3.charAt(p3);
        boolean res = false;
        //当前可能匹配p1或p2，两者都要递归
        //可能是匹配p1的
        if (p1 < s1.length() && s1.charAt(p1) == c) {
            res = res || process(p1 + 1, s1, p2, s2, p3 + 1, s3);
        }
        //可能是匹配p2的
        if (p2 < s2.length() && s2.charAt(p2) == c) {
            res = res || process(p1, s1, p2 + 1, s2, p3 + 1, s3);
        }
        //二者都不匹配，不会进入递归，直接是false
        return res;
    }

    /**
     * 思路4：利用3个指针匹配，注意s3处可能匹配到s1或s2，都要考虑，所以采用递归
     * 重复计算的地方：
     * p1 = 1, p2 = 3,下一次处理 p1=1,p2=4
     * p1 = 0, p2 = 4,下一次处理 p1=1,p2=4
     * <p>
     * memo[p1][p2]带表s1匹配到p1，s2匹配到p2能否完成整个匹配
     */
    public static boolean isInterleave4(String s1, String s2, String s3) {

        if (s1.length() + s2.length() != s3.length()) return false;
        if (s1.isEmpty() || s2.isEmpty()) {
            return s1.isEmpty() ? s2.equals(s3) : s1.equals(s3);
        }
        int[][] memo = new int[s1.length()][s2.length()]; //default 0
        return process(0, s1, 0, s2, 0, s3, memo);
    }

    private static boolean process(int p1, String s1, int p2, String s2, int p3, String s3,
                                   int[][] memo) {
        if (p3 == s3.length()) return true;
        if (p1 == s1.length()){
            return s2.substring(p2,s2.length()).equals(s3.substring(p3,s3.length()));
        }
        if(p2 == s2.length()){
            return s1.substring(p1,s1.length()).equals(s3.substring(p3,s3.length()));
        }

        if (memo[p1][p2] != 0)
            return memo[p1][p2] == 1;

        char c = s3.charAt(p3);
        boolean res = false;
        //当前可能匹配p1或p2，两者都要递归
        //可能是匹配p1的
        if (p1 < s1.length() && s1.charAt(p1) == c) {
            res = res || process(p1 + 1, s1, p2, s2, p3 + 1, s3, memo);
        }
        //可能是匹配p2的
        if (p2 < s2.length() && s2.charAt(p2) == c) {
            res = res || process(p1, s1, p2 + 1, s2, p3 + 1, s3, memo);
        }
        //二者都不匹配，不会进入递归，直接是false，相当于剪枝了。由于剪指了，所以待记忆性的提升不明显
        memo[p1][p2] = res ? 1 : -1;
        return res;
    }

    /**
     * 思路5：dp
     * dp[i][j]表示s1匹配了i个，s2匹配了j个，能否匹配s3。 s1 的前 (i) 和 s2 的前 (j) 个字符，对应索引是i-1,j-1
     * dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)
     *           || dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)
     */
    public boolean isInterleave5(String s1, String s2, String s3) {
        if (s3.length() != s1.length() + s2.length()) {
            return false;
        }
        //注意这里是s.len+1，因为dp[0][j]和dp[i][0]有含义
        boolean dp[][] = new boolean[s1.length() + 1][s2.length() + 1];

        for (int i = 0; i <= s1.length(); i++) {
            for (int j = 0; j <= s2.length(); j++) {
                //i = 0,j = 0,p3 = 0，
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                //s1没匹配,s2和s3匹配
                } else if (i == 0) {
                    //注意s2的第j个对应的索引是 j - 1
                    dp[i][j] = dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
                } else if (j == 0) {
                    //注意第i个对应的索引是 i - 1
                    dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
                } else {
                    //第 i个和第j个对应的索引分别是 i - 1 和 j - 1
                    dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
                            || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
                }
            }
        }
        return dp[s1.length()][s2.length()];
    }
    /**
     * 空间优化
     */
    public boolean isInterleave6(String s1, String s2, String s3) {
        if (s3.length() != s1.length() + s2.length()) {
            return false;
        }
        boolean dp[] = new boolean[s2.length() + 1];
        for (int i = 0; i <= s1.length(); i++) {
            for (int j = 0; j <= s2.length(); j++) {
                if (i == 0 && j == 0) {
                    dp[j] = true;
                } else if (i == 0) {
                    dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
                } else if (j == 0) {
                    dp[j] = dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
                } else {
                    dp[j] = (dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
                }
            }
        }
        return dp[s2.length()];
    }


}
